package com.company.algo.DichotomousSearch;

import java.util.Arrays;

public class ShipWithinDays {
    public int shipWithinDays(int[] weights, int days) {
        //承重可能的最小值
        int left = Arrays.stream(weights).max().getAsInt();
        // 载重可能的最大值 + 1
        int right = Arrays.stream(weights).sum() + 1;
        while (left < right){
            int mid = left + (right - left) / 2;
            if (canFinish(weights,days,mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    // 如果载重为 cap，是否能在 D 天内运完货物？
    private boolean canFinish(int[] weights, int D, int cap) {
        int i = 0;
        for(int day = 0; day < D; day++){
            int maxCap = cap;
            while ((maxCap-=weights[i])>=0){
                i++;
                if (i == weights.length) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        ShipWithinDays Main = new ShipWithinDays();
        int[] weights = {1,3,4,2,4};
        int days = 3;
        System.out.println(Main.shipWithinDays(weights, days));
    }
}
